|
課程名稱 |
組合學一
Combinatorics(Ⅰ) |
|
開課學期 |
99-2 |
|
授課對象 |
理學院 數學研究所 |
|
授課教師 |
張鎮華 |
|
課號 |
MATH7701 |
|
課程識別碼 |
221 U3290 |
|
班次 |
|
|
學分 |
3 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
星期二1,2(8:10~10:00)星期四2(9:10~10:00) |
|
上課地點 |
天數102天數102 |
|
備註 |
總人數上限：30人 |
|
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/992combinatorics |
|
課程簡介影片 |
|
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
1. Graphs. 2. Trees. 3. Colorings of graphs and Ramsey’s theorem. 4. Turan’s theorem and extremal graphs. 5. Systems of distinct representatives. 6. Dilworth’s theorem and extremal set theory. 7. Flows in networks. 8. De Bruijn sequences. 9. Two (0,1,*) problems: addressing for graphs and a hash-coding scheme. 10. The principle of inclusion and exclusion; inversion formula. 11. Permanents. 12. The van der Waerden conjecture. 13. Elementary counting; Stirling numbers. 14. Recursions and generating functions. 15 Partitions. 16. (0,1)-Matrices. 17. Latin squares. 18. Hadamard matrices, Reed-Muller codes. 19. Designs. 20. Codes and designs. 21. Strongly regular graphs and partial geometries. 22. Orthogonal Latin squares. 23. Projective and combinatorial geometries. 24. Gaussian numbers and q-analogues. 25. Lattices and Mobius inversion. 26. Combinatorial designs and projective geometries. 27. Difference sets and automorphsims. 28. Difference sets and the group ring. 29. Codes and symmetric designs. 30. Association schemes. 31. (More) algebraic techniques in graph theory. 32. Graph connectivity. 33. Planarity and coloring. 34. Whitney Duality. 35. Embeddings of graphs on surfaces. 36. Electrical networks and squared squares. 37. Polya theory of counting. 38. Baranyai’s theorem. |
|
課程目標 |
Combinatorics is a subject dealing with ways of arranging and distributing objects. It involves ideas from geometry, algebra and analysis. This course is to introduce basic idea of combinatorics by means of example topics as listed above. |
|
課程要求 |
|
|
預期每週課後學習時數 |
|
|
Office Hours |
|
|
指定閱讀 |
J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Second Edition, Cambridge University Express, 2001. |
|
參考書目 |
|
|
評量方式
(僅供參考) |
|
No. |
項目 |
百分比 |
說明 |
|
1. |
期中 |
35% |
|
2. |
期末 |
35% |
|
3. |
作業 |
30% |
|
|
|
週次 |
日期 |
單元主題 |
|
第1週 |
2/22,2/24 |
1. Graphs. 2. Trees. |
|
第2週 |
3/01,3/03 |
3. Colorings of graphs and Ramsey’s theorem. 4. Turan’s theorem and extremal graphs. |
|
第3週 |
3/08,3/10 |
5. Systems of distinct representatives. 6. Dilworth’s theorem and extremal set theory. |
|
第4週 |
3/15,3/17 |
7. Flows in networks. 8. De Bruijn sequences. |
|
第5週 |
3/22,3/24 |
9. Two (0,1,*) problems: addressing for graphs and a hash-coding scheme. 10. The principle of inclusion and exclusion; inversion formula. |
|
第6週 |
3/29,3/31 |
11. Permanents. 12. The van der Waerden conjecture. |
|
第7週 |
4/05,4/07 |
13. Elementary counting; Stirling numbers. 14. Recursions and generating functions. |
|
第8週 |
4/12,4/14 |
15 Partitions. 16. (0,1)-Matrices. |
|
第9週 |
4/19,4/21 |
17. Latin squares. 18. Hadamard matrices, Reed-Muller codes. (Midterm Exam on 4/23 Saturday 18:00 ~ ) |
|
第10週 |
4/26,4/28 |
19. Designs. 20. Codes and designs. |
|
第11週 |
5/03,5/05 |
21. Strongly regular graphs and partial geometries. 22. Orthogonal Latin squares. |
|
第12週 |
5/10,5/12 |
23. Projective and combinatorial geometries. (Chpater 23 is skipped) 24. Gaussian numbers and q-analogues. |
|
第13週 |
5/17,5/19 |
25. Lattices and Mobius inversion. 26. Combinatorial designs and projective geometries. (Chapter 26 is skipped.) |
|
第14週 |
5/24,5/26 |
27. Difference sets and automorphsims. 28. Difference sets and the group ring. (Chapter 27 and 28 are skippped.) |
|
第15週 |
5/31,6/02 |
29. Codes and symmetric designs. 30. Association schemes. (Chapters 29 and 30 are skpped.) |
|
第16週 |
6/07,6/09 |
31. (More) algebraic techniques in graph theory. 32. Graph connectivity. 33. Planarity and coloring. |
|
第17週 |
6/14,6/16 |
34. Whitney Duality. 35. Embeddings of graphs on surfaces. 36. Electrical networks and squared squares. |
|
第18週 |
6/21,6/23 |
37. Polya theory of counting. 38. Baranyai’s theorem. Final exam on 6/23 (Thursday) 8:00--10:00 |
|